package basic;

import java.util.TreeMap;

/**
 * Created on 2019/10/25.
 */
public class BinarySearchTree {

    public static void main(String[] args) {
        Node p = new Node(33);
        Node node16 = new Node(16);
        Node node50 = new Node(50);
        p.left = node16;
        p.right = node50;
        Node node18 = new Node(18);
        Node node17 = new Node(17);
        Node node25 = new Node(25);
        Node node19 = new Node(19);
        Node node27 = new Node(27);
        node16.right = node18;
        node18.left = node17;
        node18.right = node25;
        node25.left = node19;
        node25.right = node27;

        BinarySearchTree tree = new BinarySearchTree(p);
        tree.delete(18);

        //红黑树java实现
        TreeMap<String, Integer> treeMap = new TreeMap<>();

    }

    private Node tree;

    public BinarySearchTree(Node tree) {
        this.tree = tree;
    }

    //查找
    public Node find(int data) {
        Node p = tree;
        while (p != null) {
            if (data < p.data) p = p.left;
            else if (data > p.data) p = p.right;
            else return p;
        }
        return null;
    }

    //插入
    public void insert(int data) {
        if (tree == null) {
            tree = new Node(data);
            return;
        }

        Node p = tree;
        while (p != null) {
            if (data > p.data) {
                if (p.right == null) {
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            } else { // data < p.data
                if (p.left == null) {
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            }
        }
    }

    //删除
    public void delete(int data) {
        Node p = tree; // p 指向要删除的节点，初始化指向根节点
        Node pp = null; // pp 记录的是 p 的父节点
        while (p != null && p.data != data) {
            pp = p;
            if (data > p.data) p = p.right;
            else p = p.left;
        }
        if (p == null) return; // 没有找到

        // 要删除的节点有两个子节点
        if (p.left != null && p.right != null) { // 查找右子树中最小节点
            Node minP = p.right;
            Node minPP = p; // minPP 表示 minP 的父节点
            while (minP.left != null) {
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.data; // 将 minP 的数据替换到 p 中
            p = minP; // 下面就变成了删除 minP 了
            pp = minPP;
        }

        // 删除节点是叶子节点或者仅有一个子节点
        Node child; // p 的子节点
        if (p.left != null) child = p.left;
        else if (p.right != null) child = p.right;
        else child = null;

        if (pp == null) tree = child; // 删除的是根节点
        else if (pp.left == p) pp.left = child;
        else pp.right = child;
    }


    public static class Node {
        private int data;
        private Node left;
        private Node right;

        public Node(int data) {
            this.data = data;
        }
    }

}
